Communications in Combinatorics and Optimization
Volume:8 Issue: 3, Summer 2023

In this paper, we introduce the notion of normalized distance Laplacian matrices for signed graphs corresponding to the two signed distances defined for signed graphs. We characterize balance in signed graphs using these matrices and compare the normalized distance Laplacian spectral radius of signed graphs with that of all-negative signed graphs. Also we characterize the signed graphs having maximum normalized distance Laplacian spectral radius.

Let $D$ be a finite and simple digraph with vertex set $V(D)$. A signed total Italian dominating function (STIDF) on a digraph $D$ is a function $f:V(D)rightarrow{-1,1,2}$ satisfying the conditions that (i) $sum_{xin N^-(v)}f(x)ge 1$ for each $vin V(D)$, where $N^-(v)$ consists of all vertices of $D$ from which arcs go into $v$, and (ii) every vertex $u$ for which $f(u)=-1$ has an in-neighbor $v$ for which $f(v)=2$ or two in-neighbors $w$ and $z$ with $f(w)=f(z)=1$. The weight of an  STIDF $f$ is $sum_{vin V(D)}f(v)$. The signed total Italian domination number $gamma_{stI}(D)$ of $D$ is the minimum weight of an STIDF on $D$. In this paper we initiate the study of the signed total Italian domination number of digraphs, and we  present different bounds on $gamma_{stI}(D)$. In addition, we determine the signed total Italian domination number of some classes of digraphs.

A Roman dominating function (RDF) on a graph $G$ is a function $f: V(G) to {0, 1, 2}$ such that every vertex with label 0 has a neighbor with label 2. A vertex $u$ with $f(u)=0$ is said to be undefended if it is not adjacent to a vertex with $f(v)>0$. The function $f:V(G) to {0, 1, 2}$ is a weak Roman dominating function (WRDF) if each vertex $u$ with $f(u) = 0$ is adjacent to a vertex $v$ with $f(v) > 0$ such that the function $f^{prime}: V(G) to {0, 1, 2}$ defined by $f^{prime}(u) = 1$, $f^{prime}(v) = f(v) - 1$ and $f^{prime}(w) = f(w)$ if $w in V - {u, v}$, has no undefended vertex. A graph $G$ is said to be Roman domination stable upon edge addition, or just $gamma_R$-EA-stable, if $gamma_R(G+e)= gamma_R(G)$ for any edge $e notin E(G)$. We extend this concept to a weak Roman dominating function as follows: A graph $G$ is said to be weak Roman domination stable upon edge addition, or just $gamma_r$-EA-stable, if $gamma_r(G+e)= gamma_r(G)$ for any edge $e notin E(G)$. In this paper, we study $gamma_r$-EA-stable graphs, obtain bounds for  $gamma_r$-EA-stable graphs and  characterize $gamma_r$-EA-stable trees which attain the bound.

Let G = (V,E) be a connected graph of order n. A path P in G which does not have a chord is called a monophonic path. A subset S of V is called a monophonic set if every vertex v in V lies in a x-y monophonic path where x, y 2 S. If further the induced subgraph G[S] has no isolated vertices, then S is called a total monophonic set. The total monophonic number mt(G) and the upper total monophonic number m+t (G) are respectively the minimum cardinality of a total monophonic set and the maximum cardinality of a minimal total monophonic set. In this paper we determine the value of these parameters for some classes of graphs and establish bounds for the same. We also prove the existence of graphs with prescribed values for mt(G) and m+t (G).

Let $G=(V,E)$ be a graph.  A double Roman dominating function  (DRDF) of   $G $   is a function   $f:Vto {0,1,2,3}$  such that, for each $vin V$ with $f(v)=0$,  there is a vertex $u $  adjacent to $v$  with $f(u)=3$ or there are vertices $x$ and $y $  adjacent to $v$  such that  $f(x)=f(y)=2$ and for each $vin V$ with $f(v)=1$,  there is a vertex $u $    adjacent to $v$    with  $f(u)>1$.  The weight of a DRDF $f$ is   $ f (V) =sum_{ vin V} f (v)$.   Let $n$ and  $k$ be integers such that  $3leq 2k+ 1  leq n$.  The   generalized Petersen graph $GP (n, k)=(V,E) $  is the  graph  with  $V={u_1, u_2,ldots,  u_n}cup{v_1, v_2,ldots, v_n}$ and $E={u_iu_{i+1}, u_iv_i, v_iv_{i+k}:  1 leq i leq n}$, where  addition is taken  modulo $n$. In this paper,  we firstly   prove that the  decision     problem  associated with   double Roman domination is NP-omplete even restricted to planar bipartite graphs with maximum degree at most 4.  Next, we   give  a dynamic programming algorithm for  computing a minimum DRDF (i.e., a  DRDF   with minimum weight  along  all   DRDFs)  of $GP(n,k )$  in $O(n81^k)$ time and space  and so a  minimum DRDF  of $GP(n,O(1))$  can be computed in $O( n)$ time and space.

For a graph $G=(V,E)$, a triple Roman dominating function (3RD-function) is a function $f:Vto {0,1,2,3,4}$ having the property that (i) if $f(v)=0$ then $v$ must have either one neighbor $u$ with $f(u)=4$, or two neighbors $u,w$ with $f(u)+f(w)ge 5$ or three neighbors $u,w,z$ with $f(u)=f(w)=f(z)=2$, (ii) if $f(v)=1$ then $v$ must have one neighbor $u$ with $f(u)ge 3$ or two neighbors $u,w$ with $f(u)=f(w)=2$, and (iii) if $f(v)=2$ then $v$ must have one neighbor $u$ with $f(u)ge 2$. The weight of a 3RDF $f$ is the sum $f(V)=sum_{vin V} f(v)$, and the minimum weight of a 3RD-function on $G$ is the triple Roman domination number of $G$, denoted by $gamma_{[3R]}(G)$. In this paper, we prove that for any connected graph $G$ of order $n$ with minimum degree at least two,  $gamma_{[3R]}(G)leq frac{3n}{2}$.

In this paper, we explore several properties of Sombor coindex of a finite simple graph and we derive a bound for the total Sombor index. We also explore its relations to the Sombor index, the Zagreb coindices, forgotten coindex and other important graph parameters. We further compute the bounds of the Somber coindex of some graph operations and derived explicit formulae of Sombor coindex for some well-known graphs as application.

We consider a stochastic convex optimization problem over nonsymmetric cones with discrete support. This class of optimization problems has not been studied yet. By using a logarithmically homogeneous self-concordant barrier function, we present a homogeneous predictor-corrector interior-point algorithm for solving stochastic nonsymmetric conic optimization problems. We also derive an iteration bound for the proposed algorithm. Our main result is that we uniquely combine a nonsymmetric algorithm with efficient methods for computing the predictor and corrector directions. Finally, we describe a realistic application and present computational results for instances of the stochastic facility location problem formulated as a stochastic nonsymmetric convex conic optimization problem.

For a commutative ring $R$ with identity $1neq 0$, let the set $Z(R)$ denote the set of zero-ivisors and let $Z^{*}(R)=Z(R)setminus {0}$ be the set of non-zero zero-divisors of $R$.  The zero-divisor graph of $R$, denoted by $Gamma(R)$, is a simple graph whose vertex set is $Z^{*} (R)$ and two vertices $u, v in Z^*(R)$ are adjacent if and only if $uv=vu=0$. In this article, we find the signless Laplacian spectrum of the zero divisor graphs $ Gamma(mathbb{Z}_{n}) $ for $ n=p^{M_{1}}q^{M_{2}}$, where $ p<q $ are primes and $ M_{1} , M_{2} $ are positive integers.

Let $G$ be a graph with vertex set $V(G)$. A Roman dominating function  (RDF) on a graph $G$ is a function $f:V(G)longrightarrow{0,1,2}$ such that every vertex $v$  with $f(v)=0$ is adjacent to a vertex  $u$ with $f(u)=2$. If $f$ is an RDF on $G$, then let $V_i={vin V(G): f(v)=i}$ for $iin{0,1,2}$. An RDF $f$ is called a restrained (total) Roman dominating function if the subgraph induced by $V_0$  (induced by $V_1cup V_2$) has no isolated vertex. A total and restrained Roman dominating function is a total restrained Roman  dominating function.  The total restrained Roman domination number $gamma_{trR}(G)$ on a graph $G$ is the minimum weight of a total restrained Roman dominating function on the graph $G$. We initiate the study of total restrained Roman domination number and present several sharp bounds on $gamma_{trR}G)$. In addition, we determine this parameter for some classes of graphs.

A facial total-coloring of a plane graph $G$ is a coloring of the vertices and edges such that no facially adjacent edges, no adjacent vertices, and no edge and its endvertices are assigned the same color. A facial total-coloring of $G$ is odd if for every face $f$ and every color $c$, either no element or an odd number of elements incident with $f$ is colored by $c$. In this note we prove that every cactus forest with an outerplane embedding admits an odd facial total-coloring with at most 16 colors. Moreover, this bound is tight.

A type $(1,1,1)$ face-magic labeling of a planar graph $G=(V,E,F)$  is a bijection from $Vcup E cup F$ to the set of labels ${1,2,dots,|V|+|E|+|F|}$ such that the weight of every $n$-sided face of $G$ is equal to the same fixed constant. The weight of a face $mathcal{F} in F$ is equal to the sum of the labels of the vertices, edges, and face that determine $mathcal{F}$. It is known that the grid graph $P_m square P_n$ admits a type $(1,1,1)$ face-magic labeling, but the proof in the literature is quite lengthy. We give a simple proof of this result and show two more infinite families of gridded graphs admit type $(1,1,1)$ face-magic labelings.